///////////////////////////////////////////////////////////////////////////////
///  Graph.cpp
///  <TODO: insert file description here>
///
///  @remarks <TODO: insert remarks here>
///
///  @author Yan Qi @date 8/18/2010
/// 
///  $Id: Graph.cpp 65 2010-09-08 06:48:36Z yan.qi.asu $
///////////////////////////////////////////////////////////////////////////////

#include <limits>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <fstream>
#include <iostream>
#include <algorithm>
#include <math.h>
#include "GraphElements.h"
#include "Graph.h"
#include "TSPCostMatrix.h"
#include "Solution.h"
#include "TSPPath.h"
#include "TSPPathMatrix.h"
#include "GlobalDefs.h"

const double Graph::DISCONNECT = (numeric_limits<double>::max)();

Graph::Graph(const TSPCostMatrix &costs,
		const vector<unsigned int> &nodos_endpoints,
		const vector<unsigned int> &nodos_resto, unsigned int nodo_v) {
	_import_from_TSP(costs, nodos_endpoints, nodos_resto, nodo_v);
}

Graph::Graph(const Solution &sol) {
	_import_from_TSP(sol);
}

Graph::Graph(const vector<unsigned int> &nodos_fijos,
		const TSPCostMatrix &costs, const Solution &sol, TSPPathMatrix &P) {
	_import_from_TSP(nodos_fijos, costs, sol, P);
}

Graph::Graph(const string& file_name) {
	_import_from_file(file_name);
}

Graph::Graph(const Graph& graph) {
	m_nVertexNum = graph.m_nVertexNum;
	m_nEdgeNum = graph.m_nEdgeNum;
	m_vtVertices.assign(graph.m_vtVertices.begin(), graph.m_vtVertices.end());
	m_mpFaninVertices.insert(graph.m_mpFaninVertices.begin(),
			graph.m_mpFaninVertices.end());
	m_mpFanoutVertices.insert(graph.m_mpFanoutVertices.begin(),
			graph.m_mpFanoutVertices.end());
	m_mpEdgeCodeWeight.insert(graph.m_mpEdgeCodeWeight.begin(),
			graph.m_mpEdgeCodeWeight.end());
	m_mpVertexIndex.insert(graph.m_mpVertexIndex.begin(),
			graph.m_mpVertexIndex.end());
}

Graph::~Graph(void) {
	clear();
}

///////////////////////////////////////////////////////////////////////////////
///  public  _import_from_file
///  Construct the graph by importing the edges from the input file. 
///
///  @param [in]       file_name const std::string &    The input graph file
///
///  This function doesn't return a value
///
///  @remarks The format of the file is as follows:
///   1. The first line has an integer as the number of vertices of the graph
///   2. Each line afterwards contains a directed edge in the graph:
///		     starting point, ending point and the weight of the edge. 
///		 These values are separated by 'white space'.
///
///  @see <TODO: insert text here>
///
///  @author Yan Qi @date 5/29/2010
///////////////////////////////////////////////////////////////////////////////
void Graph::_import_from_file(const string& input_file_name) {
	const char* file_name = input_file_name.c_str();

	//1. Check the validity of the file
	ifstream ifs(file_name);
	if (!ifs) {
		cerr << "The file " << file_name << " can not be opened!" << endl;
		exit(1);
	}

	//2. Reset the members of the class
	clear();

	//3. Start to read information from the input file. 
	/// Note the format of the data in the graph file.
	//3.1 The first line has an integer as the number of vertices of the graph
	ifs >> m_nVertexNum;

	//3.2 In the following lines, each line contains a directed edge in the graph:
	///   the id of starting point, the id of ending point, the weight of the edge. 
	///   These values are separated by 'white space'. 
	int start_vertex, end_vertex;
	double edge_weight;
	int vertex_id = 0;

	while (ifs >> start_vertex) {
		if (start_vertex == -1) {
			break;
		}
		ifs >> end_vertex;
		ifs >> edge_weight;

		///3.2.1 construct the vertices
		BaseVertex* start_vertex_pt = get_vertex(start_vertex);
		BaseVertex* end_vertex_pt = get_vertex(end_vertex);

		///3.2.2 add the edge weight
		//// note that the duplicate edge would overwrite the one occurring before. 
		m_mpEdgeCodeWeight[get_edge_code(start_vertex_pt, end_vertex_pt)]
				= edge_weight;

		///3.2.3 update the fan-in or fan-out variables
		//// Fan-in
		get_vertex_set_pt(end_vertex_pt, m_mpFaninVertices)->insert(
				start_vertex_pt);

		//// Fan-out
		get_vertex_set_pt(start_vertex_pt, m_mpFanoutVertices)->insert(
				end_vertex_pt);

	}

	m_nVertexNum = m_vtVertices.size();
	m_nEdgeNum = m_mpEdgeCodeWeight.size();

	ifs.close();
}

void Graph::_import_from_TSP(const TSPCostMatrix &costs, const vector<
		unsigned int> &nodos_endpoints,
		const vector<unsigned int> &nodos_resto, unsigned int nodo_v) {

	clear();
	m_nVertexNum = costs.get_node_count() + 1;

//	cout << "[DEBUG] z: " << costs.get_node_count() << endl;
//	cout << "[DEBUG] v: " << nodo_v << endl;

	set<unsigned int> asignados;
	asignados.insert(costs.get_node_count());
	asignados.insert(nodo_v);

//	cout << "[DEBUG] Construyo z-Z." << endl;
	for (unsigned int endpointIndex = 0; endpointIndex < nodos_endpoints.size(); endpointIndex++) {
		asignados.insert(nodos_endpoints[endpointIndex]);

		double edge_weight;
		edge_weight = 0.0;

//		cout << "[DEBUG] Agrego enlace desde " << costs.get_node_count()
//				<< " -> " << nodos_endpoints[endpointIndex] << " (costo: "
//				<< edge_weight << ")." << endl;

		{
			BaseVertex* start_vertex_pt = get_vertex(costs.get_node_count());
			BaseVertex* end_vertex_pt = get_vertex(
					nodos_endpoints[endpointIndex]);

			m_mpEdgeCodeWeight[get_edge_code(start_vertex_pt, end_vertex_pt)]
					= edge_weight;
			get_vertex_set_pt(end_vertex_pt, m_mpFaninVertices)->insert(
					start_vertex_pt);
			get_vertex_set_pt(start_vertex_pt, m_mpFanoutVertices)->insert(
					end_vertex_pt);
		}
	}

//	cout << "[DEBUG] Construyo Z-v." << endl;
	for (unsigned int endpointIndex = 0; endpointIndex < nodos_endpoints.size(); endpointIndex++) {
		unsigned int vertex_i;
		vertex_i = nodos_endpoints[endpointIndex];

		double edge_weight;
		edge_weight = costs.get_cost(vertex_i, nodo_v);

//		cout << "[DEBUG] Agrego enlace desde " << vertex_i << " -> " << nodo_v
//				<< " (costo: " << edge_weight << ")." << endl;

		{
			BaseVertex* start_vertex_pt = get_vertex(vertex_i);
			BaseVertex* end_vertex_pt = get_vertex(nodo_v);

			m_mpEdgeCodeWeight[get_edge_code(start_vertex_pt, end_vertex_pt)]
					= edge_weight;
			get_vertex_set_pt(end_vertex_pt, m_mpFaninVertices)->insert(
					start_vertex_pt);
			get_vertex_set_pt(start_vertex_pt, m_mpFanoutVertices)->insert(
					end_vertex_pt);
		}
	}

//	cout << "[DEBUG] Construyo intra-H." << endl;
	for (unsigned int i = 0; i < nodos_resto.size(); i++) {
		asignados.insert(nodos_resto[i]);

		for (unsigned int j = 0; j < nodos_resto.size(); j++) {
			if (i != j) {
				unsigned int vertex_i;
				vertex_i = nodos_resto[i];

				unsigned int vertex_j;
				vertex_j = nodos_resto[j];

				double edge_weight;
				edge_weight = costs.get_cost(vertex_i, vertex_j);

//				cout << "[DEBUG] Agrego enlace desde " << vertex_i << " <-> "
//						<< vertex_j << " (costo: " << edge_weight << ")."
//						<< endl;

				{
					BaseVertex* start_vertex_pt = get_vertex(vertex_i);
					BaseVertex* end_vertex_pt = get_vertex(vertex_j);

					m_mpEdgeCodeWeight[get_edge_code(start_vertex_pt,
							end_vertex_pt)] = edge_weight;
					get_vertex_set_pt(end_vertex_pt, m_mpFaninVertices)->insert(
							start_vertex_pt);
					get_vertex_set_pt(start_vertex_pt, m_mpFanoutVertices)->insert(
							end_vertex_pt);
				}
				{
					BaseVertex* start_vertex_pt = get_vertex(vertex_j);
					BaseVertex* end_vertex_pt = get_vertex(vertex_i);

					m_mpEdgeCodeWeight[get_edge_code(start_vertex_pt,
							end_vertex_pt)] = edge_weight;
					get_vertex_set_pt(end_vertex_pt, m_mpFaninVertices)->insert(
							start_vertex_pt);
					get_vertex_set_pt(start_vertex_pt, m_mpFanoutVertices)->insert(
							end_vertex_pt);
				}
			}
		}
	}

//	cout << "[DEBUG] Construyo Z-H." << endl;
	for (unsigned int i = 0; i < nodos_endpoints.size(); i++) {
		for (unsigned int j = 0; j < nodos_resto.size(); j++) {
			unsigned int vertex_i;
			vertex_i = nodos_endpoints[i];

			unsigned int vertex_j;
			vertex_j = nodos_resto[j];

			double edge_weight;
			edge_weight = costs.get_cost(vertex_i, vertex_j);

//			cout << "[DEBUG] Agrego enlace desde " << vertex_i << " -> "
//					<< vertex_j << " (costo: " << edge_weight << ")." << endl;

			{
				BaseVertex* start_vertex_pt = get_vertex(vertex_i);
				BaseVertex* end_vertex_pt = get_vertex(vertex_j);

				m_mpEdgeCodeWeight[get_edge_code(start_vertex_pt, end_vertex_pt)]
						= edge_weight;
				get_vertex_set_pt(end_vertex_pt, m_mpFaninVertices)->insert(
						start_vertex_pt);
				get_vertex_set_pt(start_vertex_pt, m_mpFanoutVertices)->insert(
						end_vertex_pt);
			}
		}
	}

//	cout << "[DEBUG] Construyo H-v." << endl;
	for (unsigned int i = 0; i < nodos_resto.size(); i++) {
		unsigned int vertex_i;
		vertex_i = nodos_resto[i];

		double edge_weight;
		edge_weight = costs.get_cost(vertex_i, nodo_v);

//		cout << "[DEBUG] Agrego enlace desde " << vertex_i << " -> " << nodo_v
//				<< " (costo: " << edge_weight << ")." << endl;

		{
			BaseVertex* start_vertex_pt = get_vertex(vertex_i);
			BaseVertex* end_vertex_pt = get_vertex(nodo_v);

			m_mpEdgeCodeWeight[get_edge_code(start_vertex_pt, end_vertex_pt)]
					= edge_weight;
			get_vertex_set_pt(end_vertex_pt, m_mpFaninVertices)->insert(
					start_vertex_pt);
			get_vertex_set_pt(start_vertex_pt, m_mpFanoutVertices)->insert(
					end_vertex_pt);
		}
	}

	for (unsigned int i = 0; i < costs.get_node_count() + 1; i++) {
		if (asignados.find(i) == asignados.end()) {
//			cout << "[DEBUG] nodo " << i << " sin asignar. Lo asigno." << endl;
			{
				BaseVertex* start_vertex_pt = get_vertex(i);
				BaseVertex* end_vertex_pt = get_vertex(costs.get_node_count());

				m_mpEdgeCodeWeight[get_edge_code(start_vertex_pt, end_vertex_pt)]
						= INFINITY;
				get_vertex_set_pt(end_vertex_pt, m_mpFaninVertices)->insert(
						start_vertex_pt);
				get_vertex_set_pt(start_vertex_pt, m_mpFanoutVertices)->insert(
						end_vertex_pt);
			}
		}
	}

	m_nVertexNum = m_vtVertices.size();
	m_nEdgeNum = m_mpEdgeCodeWeight.size();
}

void Graph::_import_from_TSP(const vector<unsigned int> &nodos_fijos,
		const TSPCostMatrix &costs, const Solution &sol, TSPPathMatrix &P) {
	clear();
	m_nVertexNum = costs.get_node_count();

	for (unsigned int vertex_i = 0; vertex_i < costs.get_node_count(); vertex_i++) {
		for (unsigned int vertex_j = 0; vertex_j < vertex_i; vertex_j++) {
			if (vertex_i != vertex_j) {
				// TODO: optimizar!!!
				bool existe_en_P = false;
				for (unsigned int path_start = 0; (path_start
						< nodos_fijos.size()) && !existe_en_P; path_start++) {
					for (unsigned int path_end = 0; (path_end < path_start)
							&& !existe_en_P; path_end++) {
						//						if (DEBUG) {
						//							cout << "[DEBUG] <Graph> i: " << path_start << endl;
						//							cout << "[DEBUG] <Graph> j: " << path_end << endl;
						//						}

						if (P.get_path(path_start, path_end) != NULL) {
							existe_en_P
									= P.get_path(path_start, path_end)->contains_pair(
											vertex_i, vertex_j);
						}
					}
				}

				if (!existe_en_P) {
					double edge_weight;
					if (sol.has_link(vertex_i, vertex_j)) {
						edge_weight = 0;
					} else {
						edge_weight = costs.get_cost(vertex_i, vertex_j);
					}

					{
						BaseVertex* start_vertex_pt = get_vertex(vertex_i);
						BaseVertex* end_vertex_pt = get_vertex(vertex_j);

						m_mpEdgeCodeWeight[get_edge_code(start_vertex_pt,
								end_vertex_pt)] = edge_weight;
						get_vertex_set_pt(end_vertex_pt, m_mpFaninVertices)->insert(
								start_vertex_pt);
						get_vertex_set_pt(start_vertex_pt, m_mpFanoutVertices)->insert(
								end_vertex_pt);
					}
					{
						BaseVertex* start_vertex_pt = get_vertex(vertex_j);
						BaseVertex* end_vertex_pt = get_vertex(vertex_i);

						m_mpEdgeCodeWeight[get_edge_code(start_vertex_pt,
								end_vertex_pt)] = edge_weight;
						get_vertex_set_pt(end_vertex_pt, m_mpFaninVertices)->insert(
								start_vertex_pt);
						get_vertex_set_pt(start_vertex_pt, m_mpFanoutVertices)->insert(
								end_vertex_pt);
					}
				} else {
					{
						BaseVertex* start_vertex_pt = get_vertex(vertex_i);
						BaseVertex* end_vertex_pt = get_vertex(vertex_j);

						m_mpEdgeCodeWeight[get_edge_code(start_vertex_pt,
								end_vertex_pt)] = INFINITY;
						get_vertex_set_pt(end_vertex_pt, m_mpFaninVertices)->insert(
								start_vertex_pt);
						get_vertex_set_pt(start_vertex_pt, m_mpFanoutVertices)->insert(
								end_vertex_pt);
					}
				}
			}
		}
	}

	m_nVertexNum = m_vtVertices.size();
	m_nEdgeNum = m_mpEdgeCodeWeight.size();
}

void Graph::_import_from_TSP(const Solution &sol) {
	clear();

	m_nVertexNum = sol.get_costMatrix()->get_node_count();

	for (unsigned int vertex_i = 0; vertex_i
			< sol.get_costMatrix()->get_node_count(); vertex_i++) {
		for (unsigned int vertex_j = 0; vertex_j < vertex_i; vertex_j++) {
			if (vertex_i != vertex_j) {
				if (sol.has_link(vertex_i, vertex_j)) {
					double edge_weight;
					edge_weight = sol.get_costMatrix()->get_cost(vertex_i,
							vertex_j);

					{
						BaseVertex* start_vertex_pt = get_vertex(vertex_i);
						BaseVertex* end_vertex_pt = get_vertex(vertex_j);

						m_mpEdgeCodeWeight[get_edge_code(start_vertex_pt,
								end_vertex_pt)] = edge_weight;
						get_vertex_set_pt(end_vertex_pt, m_mpFaninVertices)->insert(
								start_vertex_pt);
						get_vertex_set_pt(start_vertex_pt, m_mpFanoutVertices)->insert(
								end_vertex_pt);
					}
					{
						BaseVertex* start_vertex_pt = get_vertex(vertex_j);
						BaseVertex* end_vertex_pt = get_vertex(vertex_i);

						m_mpEdgeCodeWeight[get_edge_code(start_vertex_pt,
								end_vertex_pt)] = edge_weight;
						get_vertex_set_pt(end_vertex_pt, m_mpFaninVertices)->insert(
								start_vertex_pt);
						get_vertex_set_pt(start_vertex_pt, m_mpFanoutVertices)->insert(
								end_vertex_pt);
					}
				} else {
					{
						BaseVertex* start_vertex_pt = get_vertex(vertex_j);
						BaseVertex* end_vertex_pt = get_vertex(vertex_i);

						m_mpEdgeCodeWeight[get_edge_code(start_vertex_pt,
								end_vertex_pt)] = INFINITY;
						get_vertex_set_pt(end_vertex_pt, m_mpFaninVertices)->insert(
								start_vertex_pt);
						get_vertex_set_pt(start_vertex_pt, m_mpFanoutVertices)->insert(
								end_vertex_pt);
					}
				}
			}
		}
	}

	m_nVertexNum = m_vtVertices.size();
	m_nEdgeNum = m_mpEdgeCodeWeight.size();
}

BaseVertex* Graph::get_vertex(int node_id) {
	if (m_stRemovedVertexIds.find(node_id) != m_stRemovedVertexIds.end()) {
		return NULL;
	} else {
		BaseVertex* vertex_pt = NULL;
		const map<int, BaseVertex*>::iterator pos = m_mpVertexIndex.find(
				node_id);
		if (pos == m_mpVertexIndex.end()) {
			int vertex_id = m_vtVertices.size();
			vertex_pt = new BaseVertex();
			vertex_pt->setID(node_id);
			m_mpVertexIndex[node_id] = vertex_pt;

			m_vtVertices.push_back(vertex_pt);
		} else {
			vertex_pt = pos->second;
		}

		return vertex_pt;
	}
}

void Graph::clear() {
	m_nEdgeNum = 0;
	m_nVertexNum = 0;

	for (map<BaseVertex*, set<BaseVertex*>*>::const_iterator pos =
			m_mpFaninVertices.begin(); pos != m_mpFaninVertices.end(); ++pos) {
		delete pos->second;
	}
	m_mpFaninVertices.clear();

	for (map<BaseVertex*, set<BaseVertex*>*>::const_iterator pos =
			m_mpFanoutVertices.begin(); pos != m_mpFanoutVertices.end(); ++pos) {
		delete pos->second;
	}
	m_mpFanoutVertices.clear();

	m_mpEdgeCodeWeight.clear();

	//clear the list of vertices objects
	for_each(m_vtVertices.begin(), m_vtVertices.end(),
			DeleteFunc<BaseVertex> ());
	m_vtVertices.clear();
	m_mpVertexIndex.clear();

	m_stRemovedVertexIds.clear();
	m_stRemovedEdge.clear();
}

int Graph::get_edge_code(const BaseVertex* start_vertex_pt,
		const BaseVertex* end_vertex_pt) const {
	/// Note that the computation below works only if 
	/// the result is smaller than the maximum of an integer!
	return start_vertex_pt->getID() * m_nVertexNum + end_vertex_pt->getID();
}

set<BaseVertex*>* Graph::get_vertex_set_pt(BaseVertex* vertex_, map<
		BaseVertex*, set<BaseVertex*>*>& vertex_container_index) {
	BaseVertexPt2SetMapIterator pos = vertex_container_index.find(vertex_);

	if (pos == vertex_container_index.end()) {
		set<BaseVertex*>* vertex_set = new set<BaseVertex*> ();
		pair<BaseVertexPt2SetMapIterator, bool> ins_pos =
				vertex_container_index.insert(make_pair(vertex_, vertex_set));

		pos = ins_pos.first;
	}

	return pos->second;
}

double Graph::get_edge_weight(const BaseVertex* source, const BaseVertex* sink) {
	int source_id = source->getID();
	int sink_id = sink->getID();

	if (m_stRemovedVertexIds.find(source_id) != m_stRemovedVertexIds.end()
			|| m_stRemovedVertexIds.find(sink_id) != m_stRemovedVertexIds.end()
			|| m_stRemovedEdge.find(make_pair(source_id, sink_id))
					!= m_stRemovedEdge.end()) {
		return DISCONNECT;
	} else {
		return get_original_edge_weight(source, sink);
	}
}

void Graph::get_adjacent_vertices(BaseVertex* vertex,
		set<BaseVertex*>& vertex_set) {
	int starting_vt_id = vertex->getID();

	if (m_stRemovedVertexIds.find(starting_vt_id) == m_stRemovedVertexIds.end()) {
		set<BaseVertex*>* vertex_pt_set = get_vertex_set_pt(vertex,
				m_mpFanoutVertices);
		for (set<BaseVertex*>::const_iterator pos = (*vertex_pt_set).begin(); pos
				!= (*vertex_pt_set).end(); ++pos) {
			int ending_vt_id = (*pos)->getID();
			if (m_stRemovedVertexIds.find(ending_vt_id)
					!= m_stRemovedVertexIds.end() || m_stRemovedEdge.find(
					make_pair(starting_vt_id, ending_vt_id))
					!= m_stRemovedEdge.end()) {
				continue;
			}
			//
			vertex_set.insert(*pos);
		}
	}
}

void Graph::get_precedent_vertices(BaseVertex* vertex,
		set<BaseVertex*>& vertex_set) {
	if (m_stRemovedVertexIds.find(vertex->getID())
			== m_stRemovedVertexIds.end()) {
		int ending_vt_id = vertex->getID();
		set<BaseVertex*>* pre_vertex_set = get_vertex_set_pt(vertex,
				m_mpFaninVertices);
		for (set<BaseVertex*>::const_iterator pos = (*pre_vertex_set).begin(); pos
				!= (*pre_vertex_set).end(); ++pos) {
			int starting_vt_id = (*pos)->getID();
			if (m_stRemovedVertexIds.find(starting_vt_id)
					!= m_stRemovedVertexIds.end() || m_stRemovedEdge.find(
					make_pair(starting_vt_id, ending_vt_id))
					!= m_stRemovedEdge.end()) {
				continue;
			}
			//
			vertex_set.insert(*pos);
		}
	}
}

double Graph::get_original_edge_weight(const BaseVertex* source,
		const BaseVertex* sink) {
	map<int, double>::const_iterator pos = m_mpEdgeCodeWeight.find(
			get_edge_code(source, sink));

	if (pos != m_mpEdgeCodeWeight.end()) {
		return pos->second;
	} else {
		return DISCONNECT;
	}
}
